/*
 * =====================================================================================
 *
 *       Filename:  BinHeap.h
 *
 *    Description:  二项式堆ADT实现
 *
 *        Version:  1.0
 *        Created:  2011-11-2 10:57:08
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

template <class Type, class Compare>
class CBinHeap
{
public:
    CBinHeap(void);
    ~CBinHeap(void);

    bool empty(void) const {
        if (head.sibling == NULL) {
            return true;
        } else {
            return false;
        }
    }

    size_t size(void) const;
    void   push(const Comparable &item);
    void   pop(void);

    Type   top (void) const {
        _Node *min = head.sibling;
        _Node *cur = head.sibling->sibling;

        while (cur) {
            if (comp(cur->element, min->element)) {
                min = cur;
            }
        }

        return min->element;
    }

    void   merge(CBinHeap &rhs) {
    }

protected:
    Compare comp;
    struct _Node {
        Type  element;
        int   degree;
        _Node *parent;
        _Node *child;
        _Node *sibling;
    } head;

    _link(_Node *x, _Node *y) {
        x->parent = y;
        x->sibling = y->child;
        y->child = x;
        x->degree += 1;
    }
}
